############################################################
# 无监督学习
############################################################
import numpy as np


def minkowski(x, y, p):
    """
    # 求x与y的闵氏距离
    """
    return np.sum(np.abs(x-y)**p)**(1/p)


def JudgeCategory(ls, centerls, p=2):
    """
    # 对ls中各样本依据与centerls中各中心距离进行分类
    """
    categoryls = []
    for i in range(ls):
        x = ls[i]
        tmpls = []  # 暂存x与各类簇中心的闵氏距离
        for y in centerls:
            tmpls.append(minkowski(x, y, p))
        j = tmpls.index(min(tmpls))     # 与x距离最近的类簇中心位置
        categoryls.append(j)
    return categoryls


def UpdateLs(k, ls, outls):
    """
    # 更新类簇中心坐标
    # k为预设分类数
    # ls为样本坐标序列
    # outls为样本分类结果序列
    """
    centerls = []
    for i in range(k):
        sum = np.zeros(len(ls[0].tolist()))     # 分类为i的样本的坐标之和
        num = 0     # 分类为i的样本的数量
        for j in range(len(ls)):
            if outls[j] == i:
                sum += ls[j]
                num += 1
        centerls.append(sum/num)
    return np.array(centerls)


def KMeans(k, ls, p=2):
    """
    # KMeans聚类算法
    # k为预设分类数
    # ls为样本坐标序列
    # p为闵氏距离度量的阶数
    """
    n = len(ls[0])      # 样本空间维数
    nmin = ls.min()     # 初始坐标最小值
    nmax = ls.max()     # 初始坐标最大值
    centerls = np.random.uniform(nmin, nmax, (k, n))     # 随机初始化k个类簇中心
    outls = [-1]*len(ls)    # 样本分类序列
    while (1):
        categoryls = JudgeCategory(ls, centerls, p)
        if outls == categoryls:
            return outls
        else:
            outls = categoryls
            centerls = UpdateLs(k, ls, outls)
